package com.example.leetcode.BFS;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 题目描述
 * 给定一个二维 0-1 矩阵，其中 1 表示陆地，0 表示海洋，每个位置与上下左右相连。已知矩
 * 阵中有且只有两个岛屿，求最少要填海造陆多少个位置才可以将两个岛屿相连。
 * 输入输出样例
 * 输入是一个二维整数数组，输出是一个非负整数，表示需要填海造陆的位置数。
 * Input:
 * [[1,1,1,1,1],
 * [1,0,0,0,1],
 * [1,0,1,0,1],
 * [1,0,0,0,1],
 * [1,1,1,1,1]]
 * Output: 1
 *
 *
 * 先用深搜添加其中一个岛，然后对这个岛进行广搜，看多少层能够搜到下一个岛
 */
public class Solution_1_934 {

    public static void main(String[] args) {
        int[][] A = new int[][]{{0,1,0}, {0,0,0},{0,0,1}};
        int[][] B = new int[][]{{1,1,1,1,1}, {1,0,0,0,1},{1,0,1,0,1},{1,0,0,0,1},{1,1,1,1,1}};

        int i = shortestBridge2(A);
    }
    // 练习1
    public static int shortestBridge2(int[][] A){

        // 1、深度优先遍历，找出一个岛,把这个岛放到一个队列里
        Deque<int[]> deque = new ArrayDeque<>();
        boolean[][] visited = new boolean[A.length][A[0].length];
        outter: for (int i = 0; i < A.length; i++) {
            for (int i1 = 0; i1 < A[0].length; i1++) {
                if (A[i][i1] == 1){
                    dfs2(A, i, i1, deque, visited);
                    break outter;
                }
            }
        }
        // 到这，第一个岛屿已经找到了，下标都在队列deque里

        // 2、基于第一个岛屿，开始进行广度优先遍历
        //通过方向，控制遍历的层数，每次只能一层
        int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int res = -1;
        return bfs(deque, res, directions, A, visited);
    }
    /**
     * 不能使用回溯法，因为你第一次找到了岛屿的面积，实际上就应该结束了，但是你没法结束，因为你不知道岛屿的面积是多少，设置不了条件，无法推出递归
     * 然后回溯到之前的状态，被回溯的单元格，就被标记为未访问的状态，又会重新访问，导致求出来的岛屿会有重复
     *
     * 回溯法适合于，排列、组合、选择类问题使用回溯法比较方便
     *
     * 像这种找岛屿，求面积之类的，直接使用visited来标记是否被访问过，来进行深搜就行
     */
    private static void dfs2(int[][] a, int i, int j, Deque<int[]> deque, boolean[][] visited) {
        // 当前的元素必须在二维数组上,并且元素不等于0,并且没有被访问过，才能被添加到队列里
        if (i < 0 || j < 0 || i >= a.length || j >= a[0].length  || visited[i][j] || a[i][j] == 0){
            return ;
        }

        visited[i][j] = true;
        deque.add(new int[]{i, j});

        // 向其他方向找元素,上下左右
        dfs2(a, i - 1, j, deque,visited);
        dfs2(a, i + 1, j, deque,visited);
        dfs2(a, i, j - 1, deque,visited);
        dfs2(a, i, j + 1, deque,visited);
    }
    private static int bfs(Deque<int[]> deque, int res ,int[][] directions,int[][] a,boolean[][] visited){
        // 遍历当前队列里的元素
        while(!deque.isEmpty()){
            int size = deque.size();
            // 层数+1
            res ++;
            // 遍历当前队列
            for (int i = 0; i < size; i++) {
                // 获取当前元素
                int[] poll = deque.poll();
                // 遍历方向
                for (int j = 0; j < 4; j++) {
                    int new_x =  poll[0] + directions[j][0];
                    int new_y = poll[1] + directions[j][1];

                    //新的点，要在二维数组上，并且没有访问过
                    if (new_x < 0 || new_y < 0 || new_x >= a.length || new_y >= a[0].length || visited[new_x][new_y]){
                        continue;
                    }
                    // 找到最短路径了
                    if(a[new_x][new_y] == 1){
                        return res;
                    }
                    // 标记当前元素为访问过
                    visited[new_x][new_y] = true;
                    // 将下一层的元素，添加到队列里
                    deque.add(new int[]{new_x,new_y});
                }
            }
        }
        return res;
    }


}